package util;

import graph.Graph;
import graph.Shrub;
import graph.Tree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Set;

/**
 *
 * @author Admin
 */
public class TreeUtils {

    public static <V, E extends Graph.Edge<V>> boolean isLocallyIrregular(Graph<V, E> graph) {
        for (V v : graph.vertices()) {
            int dv = graph.degree(v);
            for (V w : graph.neighbors(v)) {
                if (dv == graph.degree(w)) {
                    return false;
                }
            }
        }
        return true;
    }

    public static <V, E extends Graph.Edge<V>> boolean isLocallyIrregular(Tree<V, E> tree) {
        return isLocallyIrregular(tree.innerGraph());
    }

    public static <V, E extends Graph.Edge<V>> int getMaxDegree(Tree<V, E> tree) {
        int max = 0;
        for (V v : tree.nodes()) {
            int d = tree.degree(v);
            if (d > max) {
                max = d;
            }
        }
        return max;
    }

    public static <V, E extends Graph.Edge<V>> int irregularChromaticIndex(Tree<V, E> tree) {
        if (isOddLengthPath(tree)) {
            throw new IllegalArgumentException("Tree is an odd length path. Irregular chromatic index is undefined.");
        }
        if (isLocallyIrregular(tree)) {
            return 1;
        }
        int maxDegree = getMaxDegree(tree);
        if (maxDegree <= 2 || maxDegree >= 5) {
            return 2;
        }
        ArrayList<Integer> sequence = new ArrayList<Integer>();
        for (Shrub<V, E> shrub : tree.shrubs()) {
            Set<Integer> di = shrub.computeSetD0();
//            System.out.println(di);
            // di is not singleton
            if (di.size() != 1) {
                return 2;
            } else {
                sequence.add(di.iterator().next());
            }
        }
        Collections.sort(sequence);
        if (!isBadSequence(sequence)) {
            return 2;
        }
        return 3;
    }
    public static ArrayList<int[]> BAD_SEQUENCES;

    static {
        BAD_SEQUENCES = new ArrayList<int[]>();
        BAD_SEQUENCES.add(new int[]{1});
        BAD_SEQUENCES.add(new int[]{1, 2});
        BAD_SEQUENCES.add(new int[]{2, 2, 3});
        BAD_SEQUENCES.add(new int[]{2, 3, 3, 4});

    }

    private static boolean isBadSequence(ArrayList<Integer> sequence) {
        for (int[] array : BAD_SEQUENCES) {
            if (sequence.size() == array.length) {
                for (int i = 0; i < array.length; i++) {
                    if (sequence.get(i) != array[i]) {
                        return false;
                    }
                }
                return true;
            }
        }
        return false;
    }

    public static <V, E extends Object & Graph.Edge<V>> boolean isOddLengthPath(Tree<V, E> tree) {
        int length = 0;
        V v = tree.root();
        while (true) {
            // count number of children
            int count = 0;
            for (V child : tree.children(v)) {
                v = child;
                count++;
                // more than one children => not unique path
                if (count > 1) {
                    return false;
                }
            }
            // no children
            if (count == 0) {
                break;
            }
            length++;
        }
        return length % 2 == 1;
    }
}
